package week_05;

import java.util.*;
import java.util.stream.*;

/**
 * 56. 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 * <p>
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */
public class MergeIntervals_56 {

    public int[][] merge_with_differ(int[][] intervals) {
        // 先处理差分事件
        List<int[]> events = new ArrayList<>();
        for (int[] item : intervals) {
            events.add(new int[]{item[0], 1});
            events.add(new int[]{item[1], -1});
        }
        Collections.sort(events, (event1, event2) -> event1[0] == event2[0] ?
                event2[1] - event1[1] : event1[0] - event2[0]);

        List<int[]> ans = new ArrayList<>();
        int start = events.get(0)[0];
        int count = 0;
        for (int[] item : events) {
            if (count == 0) {
                start = item[0];
            }
            count += item[1];
            if (count == 0) {
                ans.add(new int[]{start, item[0]});
            }
        }
        return ans.toArray(new int[ans.size()][2]);
    }

    public int[][] merge_sort_interval(int[][] intervals) {
        // 先求sort
        List<int[]> intervalList = new ArrayList<>();
        for (int[] item : intervals) {
            intervalList.add(new int[]{item[0], item[1]});
        }
        Collections.sort(intervalList, (interval1, interval2) -> interval1[0] == interval2[0] ?
                interval1[1] - interval2[1] : interval1[0] - interval2[0]);

        List<int[]> ans = new ArrayList<>();
        int left = intervalList.get(0)[0];
        int far = intervalList.get(0)[1];
        for (int[] item : intervalList) {
            int start = item[0];
            int end = item[1];
            if (start <= far) {
                far = Math.max(far, end);
            } else {
                if (far > -1) ans.add(new int[]{left, far});
                left = start;
                far = end;
            }
        }
        if (far > -1) ans.add(new int[]{left, far});
        return ans.toArray(new int[ans.size()][2]);
    }


    public static void main(String[] args) {
        MergeIntervals_56 test = new MergeIntervals_56();
        int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        test.merge_with_differ(intervals);
    }
}
